package com.practice.niuke.new_direct_basics.class05;

import java.util.HashMap;
import java.util.HashSet;

public class Code07_LowestCommonAncestor {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 给定两个二叉树的节点node1和node2， 找到他们的最低公共祖先节点时，
     * 递归函数作用于每个节点返回的统一信息：
     * <f>
     * （1）boolean findO1: 整棵树上是否发现了o1
     * （2）boolean findO2: 整棵树上是否发现了o2
     * （3）Node findAns:   整棵树上是否发现了o1和o2的最低公共祖先findAns
     */
    public static class Info {
        public boolean findO1;
        public boolean findO2;
        public Node findAns;

        public Info(boolean findO1, boolean findO2, Node findAns) {
            this.findO1 = findO1;
            this.findO2 = findO2;
            this.findAns = findAns;
        }
    }

    /**
     * 递归函数：以x为头的树，返回Info1（3个信息）
     *
     * @param x 节点
     * @return Info
     */
    public static Info process(Node x, Node o1, Node o2) {
        if (x == null) {
            return new Info(false, false, null);
        }
        // x节点的左子树（不包括x节点）返回的三个信息
        Info leftInfo = process(x.left, o1, o2);
        // x节点的右子树（不包括x节点）返回的三个信息
        Info rightInfo = process(x.right, o1, o2);

        // 1、x节点的左子树（不包括x节点） 或者 x节点的右子树（不包括x节点）同时发现o1和o2

        // 1.1、x节点的左子树（不包括x节点）发现了最低公共祖先
        if (leftInfo.findAns != null) {
            return new Info(true, true, leftInfo.findAns);
        }
        // 1.2、x节点的右子树（不包括x节点）发现了最低公共祖先
        if (rightInfo.findAns!=null){
            return new Info(true, true, rightInfo.findAns);
        }

        // 2、x节点的左子树（不包括x节点） 和 x节点的右子树（不包括x节点）
        // 都没有发现最低公共祖先(都没有同时发现o1和o2)，但是都分别发现了o1或者o2

        // 2.1、在x节点的左子树（不包括x节点）上发现了o1，在x节点的右子树（不包括x节点）上发现了o2，
        // 当前的x就是最低公共祖先
        if (leftInfo.findO1 && rightInfo.findO2){
            return new Info(true, true, x);
        }
        // 2.2、在x节点的左子树（不包括x节点）上发现了o2，在x节点的右子树（不包括x节点）上发现了o1，
        // 当前的x就是最低公共祖先
        if (leftInfo.findO2 && rightInfo.findO1){
            return new Info(true, true, x);
        }

        // 3、x节点的左子树（不包括x节点） 和 x节点的右子树（不包括x节点），
        // 都没有发现最低公共祖先(都没有同时发现o1和o2)，
        // 且左子树或者右子树只发现了o1或者o2（最低公共祖先不在x处交汇），或者什么都没有发现。

        boolean findO1 = (x == o1);// x处是否为o1
        boolean findO2 = (x == o2);// x处是否为o2
        // 3.1、x节点的左子树（不包括x节点）发现o1 或者 x节点的右子树（不包括x节点）发现o1
        if (leftInfo.findO1 || rightInfo.findO1){
            if (findO2){
                // x处为o2, 则最低公共祖先在x处
                return new Info(true, true, x);
            }else {
                return new Info(true, false, null);
            }
        }
        // 3.2、x节点的左子树（不包括x节点）发现o2 或者 x节点的右子树（不包括x节点）发现o2
        if (leftInfo.findO2 || rightInfo.findO2){
            if (findO1){
                // x处为o1, 则最低公共祖先在x处
                return new Info(true, true, x);
            }else {
                return new Info(false, true, null);
            }
        }
        // 4、x节点的左子树（不包括x节点） 和 x节点的右子树（不包括x节点）都没有发现o1或者o2，
        // 说明以x为头的节点的树没有发现o1和o2的最低公共祖先，
        // 而此时以x为头的节点的树是否发现了o1或者o2要看x处的节点。
        return new Info(findO1, findO2, null);
    }

    /**
     * 返回o1和o2的最低公共祖先
     *
     * @param head
     * @param o1
     * @param o2
     * @return
     */
    public static Node lowestCommon(Node head, Node o1, Node o2) {
        Info info = process(head, o1, o2);
        return info.findAns;
    }


    public static Node lowestAncestor(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) { // base case
            return head;
        }
        Node left = lowestAncestor(head.left, o1, o2);
        Node right = lowestAncestor(head.right, o1, o2);
        if (left != null && right != null) {
            return head;
        }
        // 左右两棵树，并不都有返回值
        return left != null ? left : right;
    }

    public static class Record1 {
        private HashMap<Node, Node> map;

        public Record1(Node head) {
            map = new HashMap<Node, Node>();
            if (head != null) {
                map.put(head, null);
            }
            setMap(head);
        }

        private void setMap(Node head) {
            if (head == null) {
                return;
            }
            if (head.left != null) {
                map.put(head.left, head);
            }
            if (head.right != null) {
                map.put(head.right, head);
            }
            setMap(head.left);
            setMap(head.right);
        }

        public Node query(Node o1, Node o2) {
            HashSet<Node> path = new HashSet<Node>();
            while (map.containsKey(o1)) {
                path.add(o1);
                o1 = map.get(o1);
            }
            while (!path.contains(o2)) {
                o2 = map.get(o2);
            }
            return o2;
        }

    }

    public static class Record2 {
        private HashMap<Node, HashMap<Node, Node>> map;

        public Record2(Node head) {
            map = new HashMap<Node, HashMap<Node, Node>>();
            initMap(head);
            setMap(head);
        }

        private void initMap(Node head) {
            if (head == null) {
                return;
            }
            map.put(head, new HashMap<Node, Node>());
            initMap(head.left);
            initMap(head.right);
        }

        private void setMap(Node head) {
            if (head == null) {
                return;
            }
            headRecord(head.left, head);
            headRecord(head.right, head);
            subRecord(head);
            setMap(head.left);
            setMap(head.right);
        }

        private void headRecord(Node n, Node h) {
            if (n == null) {
                return;
            }
            map.get(n).put(h, h);
            headRecord(n.left, h);
            headRecord(n.right, h);
        }

        private void subRecord(Node head) {
            if (head == null) {
                return;
            }
            preLeft(head.left, head.right, head);
            subRecord(head.left);
            subRecord(head.right);
        }

        private void preLeft(Node l, Node r, Node h) {
            if (l == null) {
                return;
            }
            preRight(l, r, h);
            preLeft(l.left, r, h);
            preLeft(l.right, r, h);
        }

        private void preRight(Node l, Node r, Node h) {
            if (r == null) {
                return;
            }
            map.get(l).put(r, h);
            preRight(l, r.left, h);
            preRight(l, r.right, h);
        }

        public Node query(Node o1, Node o2) {
            if (o1 == o2) {
                return o1;
            }
            if (map.containsKey(o1)) {
                return map.get(o1).get(o2);
            }
            if (map.containsKey(o2)) {
                return map.get(o2).get(o1);
            }
            return null;
        }

    }

    // for test -- print tree
    public static void printTree(Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.right.right.left = new Node(8);
        printTree(head);
        System.out.println("===============");

        Node o1 = head.left.right;
        Node o2 = head.right.left;

        System.out.println("o1 : " + o1.value);
        System.out.println("o2 : " + o2.value);
        System.out.println("ancestor : " + lowestAncestor(head, o1, o2).value);
        System.out.println("===============");

    }

}
